package algorithm.t202111;

import java.util.*;

/**
 * @author : 李红磊
 * @version :1.0
 * @date : 2021/11/10 8:52
 * @description :9道
 *  刷力扣一个月了，今天算是做题最多的一天。9道。明天就是一个月力扣刷题纪念日。
 *  persevere to last
 *  2021.11.10
 *  2021年11月10日21:03:16
 *  李红磊
 */
public class t20211110 {

    //495.提莫攻击
    public int findPoisonedDuration(int[] timeSeries, int duration) {
        if (duration == 0) return 0;
        int res = timeSeries.length * duration;

        for (int i = 0; i < timeSeries.length; i++) {
            if (i + 1 < timeSeries.length && timeSeries[i + 1] < timeSeries[i] + duration) {
                int gap = timeSeries[i] + duration - timeSeries[i + 1];
                res -= gap;
            }

        }


        return res;
    }

    //72.编辑距离
    public int minDistance(String word1, String word2) {
        int len1 = word1.length(), len2 = word2.length();
        int[][] dp = new int[len1 + 1][len2 + 1];


        for (int i = 0; i <= len1; i++) dp[i][0] = i;
        for (int i = 0; i <= len2; i++) dp[0][i] = i;

        for (int i = 0; i <= len1; i++) {
            for (int j = 0; j <= len2; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i - 1][j]), dp[i][j - 1]) + 1;
                }
            }
        }

        return dp[len1][len2];
    }

    //322.零钱兑换
    public int coinChange(int[] coins, int amount) {
        if (amount == 0) return 0;
        int[] dp = new int[amount + 1];//dp[i] 表示凑成面值为i需要的最少银币个数
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;//凑成面值为0需要的最少银币个数也为0

        for (int i = 1; i <= amount; i++) {
            for (int j = 0; j < coins.length; j++) {
                if (i >= coins[j]) {
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                }
            }

        }

        return dp[amount] == amount + 1 ? -1 : dp[amount];
    }

    public int coinChange2(int[] coins, int amount) {
        if (amount == 0) return 0;

        int len = coins.length;
        int[][] dp = new int[len + 1][amount + 1];//dp[i][j] 表示用前i个银币凑成面值为j所需要的最小银币数

        for (int i = 0; i <= len; i++) dp[i][0] = 0;
        for (int i = 0; i <= amount; i++) dp[0][i] = amount + 1;

        for (int i = 1; i <= len; i++) {
            for (int j = 1; j <= coins.length; j++) {
                if (i - coins[j - 1] >= 0) {
                    dp[j][i] = Math.min(dp[j - 1][i], dp[j][i - coins[j - 1]] + 1);
                }

            }
        }

        return dp[len][amount] == amount + 1 ? -1 : dp[len][amount];
    }

    //343.整数拆分
    public int integerBreak(int n) {
        int[] dp = new int[n + 1];//dp[i]表示数字i拆分出正整数的最大乘积
    /*
        对于一个数i，k假设是我们从i中拆分出来的第一个数，则剩下的部分和为i-k。
        此时由两种选择，
        1.对于剩下的i-k我们不继续拆分了，则结果就是 k*(i-k)
        2.对于剩下的i-k我们继续拆分,则结果就是 k*dp[i-k]
        例如：10 拆分出1，剩下9
        1.我们不拆分了，直接就是1*9
        2.继续拆分成，1*9的拆分
     */

        //0不是正整数，1是最小的正整数
        for (int i = 2; i <= n; i++) {
            int curMax = 0;
            for (int j = 1; j < i; j++) {
                curMax = Math.max(curMax, Math.max(j * (i - j), j * dp[i - j]));
            }
            dp[i] = curMax;
        }
        return dp[n];

    }

    //面试题16.11 跳水板
    public int[] divingBoard(int shorter, int longer, int k) {
        if (k == 0) return new int[0];
        int[] res = new int[k + 1];
        if (shorter == longer) return new int[]{longer * k};

        for (int i = k, j = 0; i >= 0 && j < res.length; i--, j++) {

            res[j] = (shorter * i) + (longer * (k - i));
        }


        return res;
    }


    //面试题16.14 最佳直线
    public int[] bestLine(int[][] points) {
        int vertical_line = 0, horizontal_line = 0, slash = 0;

        int rows = points.length, columns = points[0].length;
        List vertical = new ArrayList<Integer>();
        List horizontal = new ArrayList<Integer>();
        List slashs = new ArrayList<Integer>();

        for (int i = 0; i < rows; i++) {
            int temp = i + 1;
            while (temp < rows) {
                if (points[i][0] == points[temp][0]) {
                    vertical_line++;
                    vertical.add(i);
                    vertical.add(temp);
                } else if (points[i][1] == points[temp][1]) {
                    horizontal_line++;
                    horizontal.add(i);
                    horizontal.add(temp);
                } else if (Math.abs(points[i][0] - points[temp][0]) == Math.abs(points[i][1] - points[temp][1])) {
                    slashs.add(i);
                    slashs.add(temp);
                    slash++;
                }

                temp++;
            }
        }
        List newHorizontal = duplicate(horizontal);
        List newVertical = duplicate(vertical);
        List newSlashs = duplicate(slashs);

        newHorizontal.stream().forEach(s -> System.out.println(s));
        System.out.println();
        newVertical.stream().forEach(s -> System.out.println(s));
        newSlashs.stream().forEach(s -> System.out.println(s));
        /*System.out.println("竖线"+horizontal_line);
        System.out.println("横线"+vertical_line);
        System.out.println("斜线"+slash);*/

        return null;
    }

    private List duplicate(List<Integer> list) {
        ArrayList<Integer> newList = new ArrayList<>();
        Iterator<Integer> iterator = list.iterator();
        while (iterator.hasNext()) {
            Integer integer = iterator.next();
            if (!newList.contains(integer)) newList.add(integer);
        }
        return newList;
    }

    public int[] bestLine2(int[][] points) {
        int[] res = new int[2];
        int num = 0, maxNum = 0, len = points.length;

        for (int i = 0; i < len; i++) {

            for (int j = i + 1; j < len - 1; j++) {
                num = 2;
                if (len - 1 - j + 1 + 1 <= maxNum) break;//已经凑不够了，提前剪枝
                long x1 = points[j][0] - points[i][0];
                long y1 = points[j][1] - points[i][1];

                for (int k = j + 1; k < len; k++) {
                    long x2 = points[k][0] - points[i][0];
                    long y2 = points[k][1] - points[i][1];

                    //向量直线判断
                    if (x1 * y2 == x2 * y1) num++;

                }

                if (num > maxNum) {
                    maxNum = num;
                    res[0] = i;
                    res[1] = j;
                }

            }

        }

        return res;
    }

    //面试题16.15 珠玑妙算
    public int[] masterMind(String solution, String guess) {
        int[] res = new int[2];
        HashMap<Character, Integer> solutionMap = new HashMap<>();
        HashMap<Character, Integer> guessMap = new HashMap<>();

        for (int i = 0; i < 4; i++) {
            if (solution.charAt(i) == guess.charAt(i)) {
                res[0]++;
            } else {
                solutionMap.put(solution.charAt(i), solutionMap.getOrDefault(solution.charAt(i), 0) + 1);
                guessMap.put(guess.charAt(i), guessMap.getOrDefault(guess.charAt(i), 0) + 1);
            }
        }

        //计算伪猜中次数
        Set<Character> keySet = solutionMap.keySet();
        for (Character letter : keySet) {

            if (guessMap.containsKey(letter)) {//表面出现了【伪猜中】，（字母相同，位置同

                if (solutionMap.get(letter) == guessMap.get(letter)) {
                    res[1] += solutionMap.get(letter);

                } else if (solutionMap.get(letter) > guessMap.get(letter)) {
                    //需要将两者该字母出现的次数一致
                    while (solutionMap.get(letter) > guessMap.get(letter)) {
                        solutionMap.put(letter, solutionMap.get(letter) - 1);
                    }
                    res[1] += solutionMap.get(letter);

                } else {
                    while (solutionMap.get(letter) < guessMap.get(letter)) {
                        guessMap.put(letter, guessMap.get(letter) - 1);
                    }
                    res[1] += solutionMap.get(letter);
                }
            }

        }

        return res;
    }

    //面试题16.16 部分排序
    public int[] subSort(int[] array) {
        if (array == null || array.length < 2) return new int[]{-1, -1};

        int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
        int start = 0, end = 0, len = array.length;
        for (int i = 0; i < len; i++) {
            if (array[i] < max) {
                end = i;
            } else {
                max = Math.max(max, array[i]);
            }

            if (array[len - 1 - i] > min) {
                start = len - 1 - i;
            } else {
                min = Math.min(min, array[len - 1 - i]);
            }

        }

        if (start == 0 && end == 0) {
            return new int[]{-1, -1};
        }

        return new int[]{start, end};
    }

    //面试题16.17 连续数列
    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int len = nums.length;
        int cur = nums[0], res = cur;

        for (int i = 1; i < len; i++) {
            if (cur > 0) {
                cur += nums[i];
            } else {
                cur = nums[i];
            }
            res = Math.max(res, cur);

        }

        return res;
    }

    public static void main(String[] args) {
        t20211110 t20211110 = new t20211110();
        Arrays.stream(t20211110.masterMind("BRBB", "RBGY")).forEach(s -> System.out.println(s));
    }
}
